1. Field of the Invention
The present invention relates to a multicast message transmission device and a message receiving protocol device, which realize a fair message delivery time for a multicast message transmitted from a multicast message transmission device to a plurality of message receiving protocol devices through a communication network.
2. Description of the Background Art
A multicast communication is a communication scheme useful for applications such as a broadcasting and a distributed information processing using a communication network.
In the computer application and the information providing service, a highly reliable multicast communication scheme is required. Also, in order to take a full advantage of the characteristics of the multicast communication, there are cases in which the multicast communication is required to have a property that the identical result can be obtained at all receiver devices. This property is also applicable to a scheme for maintaining the integrity of data in a case of distributedly storing data, and a scheme for realizing a fair information providing service among subscribers.
In response to these demands, a protocol for guaranteeing the following properties has been proposed and practiced. Here, the group of receiver devices which receive the same multicast message are collectively referred to as a multicast group.
(1) Atomicity:
In a case of delivering a certain message, this message is not delivered at all unless this message is received by all the receiver devices. In other words, when a multicast message is received at one receiver device, it is guaranteed that the same multicast message is also delivered to all the other receiver device of the same multicast group.
(2) Order equivalency:
An order of receiving messages is identical among all the receiver devices of the same multicast group. The major causes for lowering the reliability in the multicast communication are a bit error in the message transmission and a discarding of the message during the message transmission. The bit error is caused by an error in a transmission path, while the discarding is caused by the congestion (the congestion in the packet network or the ATM network). As for the bit error, the message delivery failure probability can be lowered by employing the error correction technique at communicating terminals. As for the discarding, the message delivery failure probability can be lowered by carrying out the message re-transmission. Of course, the re-transmission is also effective for the message delivery failure due to the bit error, but the error correction technique is not effective for the congestion over such an extended period of time as the message is completely lost. In order to secure the reliability with respect to the congestion, the re-transmission technique is indispensable.
On the other hand, for a realization of the property that the identical receiving result can be obtained at all the receiver devices, the message delivery failure and the irregularity of the transmission delay can be obstacles. The message delivery failure can be recovered by the re-transmission as described above, but the message delivery time will be delayed when the re-transmission is carried out. Also, the transmission delay difference affects the message delivery time.
In the following, the prior art for realizing the multicast communication which satisfies the above described two properties will be described.
A device for managing the message transmission and reception in the multicast group is called a master, and a device for receiving a message is called a client, while a device for transmitting a message is called a sender. Each of the master, the client, and the sender can be conceptually divided into a functional portion for processing the multicast communication protocol and a functional portion for carrying out the multicast communication application by utilizing the protocol processing function.
Here, an exemplary case for providing the stock price information by the multicast will be considered. The application in this case corresponds to a portion for carrying out the broadcast of the stock price at the sender side, and a portion for processing the stock price information at the receiver side, such as a portion for handling the electronic stock transaction according to the stock price information for example.
The protocol processing function and the application function can be divided conceptually, but in general, they are not clearly separated in the actual implementation. In many personal computers, even when the protocol processing function and the application function are divided as the software function portions, both of these functions are executed on the same memory space by the same processor.
Now, with reference to FIG. 1, a conventional multicast receiving procedure will be described.
A master 701 transmits a message to a client-A 702 and a client-B 703 through a multicast connection. The messages are assigned with identifiers which have continuously ordered relationship. In FIG. 1, Mp denotes a message with an identifier p.
When the message Mp is received, the client-A 702 and the client-B 703 transmit acknowledge response ACKp(A) and ACKp(B) respectively to the master 701. The acknowledge response contains the message identifier p and the client identifier. There is no need to multicast this response. When the acknowledge responses ACKp(X) from all the clients (the client-A 702 and the client-B 703 in this case) are confirmed, the master 701 multicasts a message release permission RELp(i). Here, i is an identifier of a message to which the release permission is issued. This identifier is given in an order of issuing the release permission, in a manner of i, i+1, . . . .
Next, with reference to FIG. 2, a conventional multicast receiving procedure in a case of a message loss will be described. Here, the same notations as in FIG. 1 are used in FIG. 2.
The master 701 transmits the message Mp to the client-A 702 and the client-B 703 through the multicast connection. The master 701 also sets a timer T1 at a time of the transmission. The client-A 702 receives the message Mp at a time t0. On the other hand, the message to the client-B 703 is lost. In this case, the master 701 detects that the acknowledge response for the message Mp from the client-B 703 has not arrived at the time-out timing of the timer T1, and carries out the re-transmission of the message Mp. When the message Mp is received, the client-B 703 transmits the acknowledge response ACKp(B). When this acknowledge response ACKp(B) is received, the master 701 has the acknowledge responses from all the clients, so that the master 701 multicasts the message release permission RELp(i).
In the message re-transmission, the message is multicast to all the clients, and the client who received this message transmits the acknowledge response, even when the acknowledge response for the same message was already transmitted before. In this manner, even when the acknowledge response ACKp(X) is lost, the master 701 can confirm that the message is received by all the clients according to the acknowledge responses for the re-transmission after the time-out.
Next, with reference to FIG. 3, a conventional multicast receiving procedure in a case of a release permission message loss will be described. Here, the same notations as in FIG. 1 are used in FIG. 3.
FIG. 3 shows a case in which the release permission message RELp(i) for the message Mp transmitted to the client-B 703 is lost. The client-A 702 normally received the release permission message RELp(i), and the message Mp is released at a time t2.
At the client-B 703, the receiving procedure for the next message Mp+1 is normally carried out while the message Mp remains unreleased, and the client-B 703 receives the release permission message RELp+1 for that next message Mp+1. Then, the client-B 703 compares the identifier p+1 of this release permission message with the identifier p-1 of the immediately previously received release permission message, and detects the discontinuity. When the discontinuity is detected, the client-B 703 judges that the release permission message has been lost, and releases the corresponding message. In this case, the message Mp corresponding to the identifier p between p-1 and p+1 is released.
The message is released upon detecting the discontinuity of the release permission message identifiers, so that the message Mp is released before the message Mp+1, and the receiving order is maintained
Next, with reference to FIG. 4, a conventional procedure in a case of a message delivery failure will be described. Here, the same notations as in FIG. 1 are used in FIG. 4.
The master 701 transmits the message Mp to the client-A 702 and the client-B 703 through the multicast connection. The master 701 also sets the timer T1 at a time of the transmission. The client-A 702 receives the message Mp at a time t0. On the other hand, the message to the client-B 703 is lost. In this case, the master 701 detects that the acknowledge response for the message Mp from the client-B 703 has not arrived at the time-out timing of the timer T1, and carries out the re-transmission of the message Mp. When the receiving acknowledge response from the client-B 703 cannot be obtained even after this procedure is repeated for a prescribed number of times, it is regarded as the message delivery failure, and the master multicasts a transmission failure message FAILp. When this transmission failure message FAILp is received, the client-A 702 cancels the delivery of the message Mp.
Now, the conventional protocol described above has been associated with the following two problems.
(1) Unfairness due to transmission delay:
In FIG. 2, between the time t3 at which the client-A 702 receives the release permission and the time t2 at which the client-B 703 receives the release permission, there is a time difference td due to the transmission delay difference. Due to this difference, the message will be unfairly given to the respective applications at different timings.
(2) Forestalling of a message:
It is possible for the client-A 702 to read the message Mp at the time t0 immediately after receiving this message Mp. Of course, this is a violation of the protocol agreement, but whether such a violation has been committed or not cannot be checked from the other network device unless the protocol implementation is checked.
Also, even when the protocol implementation of the client device is proper, if there is a device on the network or a function within the client device which is wiretapping the message, it is possible to read the message before any other client devices can read the message. In a case of the personal computer described above, the wiretapping is possible when the application function reads out the work memory of the protocol processing, and when the receiver device is provided as a user side device, it is rather easy to add such a modification to the receiver device.
Next, with reference to FIG. 5, the prior art for realizing the identical message receiving order among all the clients in the multicast network having a plurality of senders will be described. Here, the multicast group includes a master 801, a client-A 802, a client-B 803, a sender-a 804, and a sender-b 805.
The sender-a 804 multicasts the message Mp.sup.a at a time t0. Here Mp.sup.B denotes a message having an identifier p which is transmitted from the sender-a 804, and p is a unique identifier for the sender-a 804. When this message Mp.sup.a is received, the client-A 802 and the client-B 803 transmit respective acknowledge responses ACKp.sup.a (A) and ACKp.sup.a (B) to the sender-a 804. When ACKs from all the clients are received, the sender-a 804 transmits a message release permission request RELREQp.sup.a to the master 801.
When this message release permission request RELREQp.sup.a is received, the master 801 multicasts a message release permission RELp.sup.a (i). When this message release permission RElp.sup.a (i) is received, each client releases the message.
Now, a procedure for transmitting messages of a plurality of senders is as follows.
The sender-a 804 multicasts the message Mp+1.sup.a at a time t1. Then, the sender-b 805 multicasts the message Mq.sup.b at a time t2. When these messages are received, the client-A 802 and the client-B 803 transmit respective acknowledge responses ACKp+1.sup.a (A), ACKq.sup.b (A), ACKp+1.sup.a (B) and ACKq.sup.b (B) to the sender-a 804 and the sender-b 805 respectively, and when ACKs from all the clients are received, the sender-a 804 and the sender-b 805 transmit respective message release permission requests RELREQp+1.sup.a and RELREQq.sup.b to the master 801.
Here, the message receiving order at the client-A 802 and the client-B 803 is not necessarily identical to the transmission order, because of the reasons such as the transmission delay and the delay jitter.
For each message to which the message release permission request is received, the master 801 multicasts a message release permission, in an order of receiving the message release permission requests. HEre, the message release permissions are assigned with unique identifiers i, i+1, for the multicast group. For this reason, when the client-A 802 or the client-B 803 fails to receive the message release permission, or when the receiving order is reversed, each client can detect such a receiving failure or the reversed receiving order, so that the message release order judged by the master 801 can be maintained at all the clients.
Here, the message from the sender-b 805 arrived first at the client-A 802, while the message from the sender-a 804 arrived first at the client-B 803. The sender-a 804 have to wait until the acknowledge responses from all the clients are received, so that the transmission of the message release permission request from the sender-a 804 will be later than that by the sender-b 805.
The master 801 issues the message release permissions in an order of receiving the message release permission requests, so that the message for which the message release permission request arrived at the master 801 last will be released last.
Now, the message transmitted by the sender-a 804 at the time t1 is arriving at the master 801 and the client-B 803 earlier than the message transmitted by the sender-b 805 at the later time t2. However, the message transmitted by the sender-b 805 is arriving earlier than the message transmitted by the sender-a 804 at the client-A 802. After all, the the release of the message transmitted earlier by the sender-a 804 will be later than the release of the message transmitted later by the sender-b 805 because ACKs for the message transmitted by the sender-a 804 arrive at the master 801 later.
In addition, when there is an improper implementation of the protocol, it is also possible to delay the message release time by purposefully not returning the acknowledge response for that message. Also, when the sender and the client are integrally provided, it is possible to alter the receiving order for the other clients such that as if the own message was transmitted earlier than the message sent by the other sender, by transmitting the own message only after the message from the other sender is received, and then transmitting ACK for that received message after the own message is transmitted.
As such, in the multicast protocol for a case of using a plurality of senders, the order relationship among the received messages can be maintained identically among all the clients, but the message transmission time relationship at the transmitting side is not necessarily maintained identically among different senders.
In particular, when a communication network having the transmission delay jitter is utilized, it is difficult to correct the influence due to the transmission delay jitter. Also, when the re-transmission is required, the effect similar to a case where the arrival of the message is delayed will be caused.
The multicast protocol for a case of using a plurality of senders has an unfairness due to the message delivery delay which is probabilistically caused by the transmission delay difference and the re-transmission, and it is impossible in principle to resolve this problem on the protocol based on the message identifiers. As a solution to this problem, there is a method for attaching the transmission time to the message at the sender side and determining the message receiving order at the receiver side by evaluating the attached transmission time of the message, as disclosed in Birman K., Schiper, A., Stephenson, P.: "Lightweight Causal and Atomic Group Multicast", ACM Trans. Computer Systems, 9(3), 1991.
However, in this method, it is impossible to prevent the sender from falsifying the transmission time in order to manipulate the message order.
As described, even though the atomicity and the order equivalency can be guaranteed by the multicast protocol, the conventional multicast protocol has not been fair when a time by which the application actually reads the message is accounted and a possibility for the improper protocol processing is taken into consideration. This unfairness can be an obstacle in a case of using the multicast communication for the electronic commercial transactions or for the delivery of news that can affect the transactions.
In summary, the prior art is associated with the problem of the unfairness regarding the message release time. Namely, there can be the unfairness regarding a time by which the message becomes utilizable because of the transmission delay differences.
Secondly, there is a possibility of the protocol implementation violation in the prior art. Namely, by pretending the message receiving failure, it is possible to delay the message receiving by the other receiver terminals. In addition, it is possible to deceive the other clients such that even when the own message is transmitted after the received message is read, the message order can be made to appear as reversed for the other clients.
Thirdly, there is a problem of the message wiretapping in the prior art. Namely, there is possibility for the application to read the message while the other receivers are not in a state capable of receiving the message (a receiving acknowledged state)